\chapter{预备知识}


本节介绍本论文所使用的用于多源密态数据分析的密码技术，包括安全多方计算技术和同态加密技术；以及本论文研究内容关注的用于多源数据分析的代表性算法，包括真值发现算法和动态时间扭曲算法。

\section{安全多方计算}\label{section:preliminaties_mpc}

安全多方计算（Secure Multi-Party Computation，MPC）允许相互不信任的各方在各自的私有输入上联合计算一个约定的函数，可以保障各方仅获取自己的结果，而无法从计算过程中推断其他参与方的私有输入和输出。
自从姚期智院士提出第一个安全多方计算技术以来，已有混淆电路~\cite{yao1986generate,beaver1990round,naor1999privacy,kolesnikov2008improved,zahur2015two}、秘密共享~\cite{goldreich1987play,beaver1992efficient,demmler2015aby,mohassel2018aby3}、不经意传输~\cite{brassard1986all, ishai2003extending, asharov2013more}、函数秘密共享~\cite{boyle2019secure,boyle2021Function}等多种安全多方计算技术。
本论文主要关注基于安全两方计算（2PC）的方案设计，并在本节介绍本论文研究所使用的秘密共享、不经意传输和函数秘密共享协议。

\subsection{秘密共享}

\textbf{秘密共享（Secert Sharing，SS）。}根据参与方数量和恢复秘密所需的参与方数量，可以用 $(t,n)$ 秘密共享进行定义~\cite{shamir1979share}，其中 $t\leq n$。它指的是将秘密值 $x$ 分配为 $n$ 方的共享$\{\share{x}_i\}|_{i=1}^{n}$；$x$可以从任意$t$个共享份额中恢复，例如，$\share{x}_0 \in \mathbb{Z}_p$ 和 $\share{x}_1=x-\share{x}_0 \mod p$ 是 $x\in {\mathbb{Z}_p}$的 $(2,2)$ 加法秘密共享。本论文用 $x = \rec(x_{b})$ 表示秘密共享$x$的重建过程，其中 $b \in \{0,1\}$。这个过程中，$P_{0}$ 和 $P_{1}$ 交换各自的秘密共享份额，并各自计算 $x = \share{x}_{0}^{l} + \share{x}_{1}^{l} \mod 2^{l}$ 以恢复秘密值 $x$。


\textbf{算术秘密共享（Arithmetic Secert Sharing）。}当$p\ge 2$时，也称它们为算术秘密共享。算术秘密共享的加法和常数乘法可以各方在本地进行。对于安全两方计算模型，通常使用$(2,2)$的加法算术秘密共享。要在秘密共享$\share{x}$和$\share{y}$上计算乘法$\share{z}=\share{x}\cdot \share{y}$，其中 $z=x\cdot y$，则需要在离线阶段进行预计算，以生成Beaver三元组\cite{beaver1992efficient}，用于在线阶段消耗使用。这样的预计算可以在两个不共谋的服务器之间通过同态加密或不经意传输交互进行，或者依靠一个诚实的辅助方生成。而对于无预计算的安全两方计算模型，也可以使用基于不经意传输的协议来实现秘密共享的乘法的在线计算~\cite{rathee2020cryptflow2}，但在线阶段的开销会比有预计算的模型中在线阶段的开销更大。

\textbf{布尔秘密共享（Boolean Secert Sharing）。} $(2,2)$的布尔秘密共享是将比特串按位在$\mathbb{Z}_{2}$上进行布尔逻辑运算。
Goldreich等人提出的~\cite{goldreich1987play}的GMW协议是一个典型的布尔共享协议，可以用于计算逻辑门，例如XOR和AND运算（类似于算术秘密共享的加法和乘法运算），或者计算简单的电路（例如比较器电路），以及在逻辑门之上组成的电路。


\textbf{数据表示：} 
在本论文中，主要考虑在环 $\mathbb{Z}_{2^l}$ 上使用 $(2,2)$的加法秘密共享 $\share{x}^{l}$，其中 $l$ 是一个正整数。一个值 $x$ 可以通过分割成两个份额 $\share{x}_{0}^{l}$ 和 $\share{x}_{1}^{l}$ 来完全隐藏，这两个份额分别由 $P_{0}$ 和 $P_{1}$ 持有，满足约束 $\share{x}_{0}^{l} + \share{x}_{1}^{l} = x \mod 2^{l}$。特别地，对于 $l=1$，它被视为布尔秘密共享，用 $\shareB{x}$ 表示。


与大多数使用秘密共享的工作~\cite{rathee2020cryptflow2,huang2022cheetah}一样，本论文使用定点数来表示小数。特别地，本论文用 $\mathbb{U}_{2^l}$ 表示 $l$ 位无符号整数的集合。要在 $\mathbb{U}_{2^{l}}$ 内对 $\mathbb{R}$ 中的实数 $r$ 进行编码，本论文使用定点数表示法，将 $r$ 编码为 $x = \lfloor r \cdot 2^{l'} \rfloor \mod 2^{l}$，其中 $l$ 是整数位宽，$l'$ 是缩放位数，$2^{l'}$ 是缩放因子。
对于在 $\mathbb{S}_{2^{l}}$ 中的有符号定点数 $x$，其缩放位数为 $l'$， 本论文使用 $\share{x}^{l,l'}$ 表示其对应的实数值为 $\frac{\sint{l}{x}}{2^{l'}}$，其中 $\sint{l}{x}$ 表示在 $\mathbb{U}_{2^l}$ 中以二进制补码形式表示的有符号数。
为了方便表示，本论文使用$a\equiv_{\pname{s}}b$表示有符号值$a$映射到$\mathbb{U}_{2^{l}}$中和无符号值$b$相等，其中 $a\in\mathbb{S}_{2^{l}}$且$b\in\mathbb{U}_{2^{l}}$。


\subsection{基于不经意传输的安全两方计算}\label{subsec:vectorized_2pc}

\textbf{不经意传输（Oblivious Transfer，OT）}~\cite{brassard1986all, ishai2003extending, asharov2013more}是一个安全两方协议，允许接收者从发送者的项目表$A_1,\ldots,A_n$中获取第$i$项，并对发送者隐藏$i$。为了优化不经意传输的效率，在不经意传输扩展（OT extension）~\cite{ishai2003extending,asharov2013more}中，公钥操作转移到了离线阶段，而在线阶段密码操作仅是对称密码操作。

此外，不经意传输也可以用于构建安全两方计算中一些具体协议。在CrypTFlow2~\cite{rathee2020cryptflow2}和SiRNN~\cite{rathee2021sirnn}等工作中，提供了向量化的基于不经意传输的多种函数的计算协议。本论文主要采用了~\cite{rathee2020cryptflow2,rathee2021sirnn}中最先进的基于不经意传输的函数功能。与基于另一种常见的安全两方计算技术——混淆电路相比，这些协议在并行处理大规模向量运算时具有更高的通信和计算效率。这些协议在$\mathbb{Z}_{2^l}$中的两方秘密共享之上执行，实现了逐元素的操作。除非另有说明，本论文使用粗体字母表示向量，相应的带下标的斜体字母表示向量中的元素。本论文主要使用的协议如下：


\begin{itemize}

    \item \textbf{比较协议：}
    比较功能包括 $\mathcal{F}^{\Equal}_{l}$、$\mathcal{F}^{\Less}_{l}$ 以及 $\mathcal{F}^{\LessOrEqual}_{l}$。它们都以两个秘密共享的向量 $(\share{\mathbf{x}}^{l},\share{\mathbf{y}}^{l})$ 为输入，分别返回布尔共享 $\shareB{\mathbf{E}}$，$\shareB{\mathbf{L}}$， 以及同时返回两者。这里， $E_i$ 表示 $x_{i}=y_{i}$， $L_i$ 表示 $x_{i}<y_{i}$。
    
    \item \textbf{乘法：} $\mathcal{F}^{\Multiply}_{l}(\share{\mathbf{x}}^{l,s_1},\share{\mathbf{y}}^{l,s_2})$输入两个向量$\share{\mathbf{x}}^{l,s_1}$和$\share{\mathbf{y}}^{l,s_2}$的秘密共享，其中每个元素的比特位宽为$l$，缩放位数分别为 $s_{1}$ 和 $s_{2}$。协议输出 $\share{\mathbf{z}}^{l,s_1+s_2}$，其中 $z=xy$， 并且 $z$ 的缩放因子为 $2^{s_1+s_2}$。
    
    \item \textbf{定点数截断：}
    $\mathcal{F}^{\Trunc}_{l,l'}(\share{\mathbf{x}}^{l})$ 用来减少定点数的缩放位数，输入一个各元素位宽为$l$的秘密共享向量，输出截断末尾 $l'$ 位的秘密共享向量 $\share{\mathbf{x}}^{l-l'}$，输出的每个元素是 $\mathbb{Z}_{2^{l-l'}}$ 上的秘密共享。
    
    \item \textbf{多路选择器：}
    $\mathcal{F}^{\Mux}_{l}(\shareB{\mathbf{c}},\share{\mathbf{x}}^{l})$ 输入布尔秘密共享的选择位向量 $\shareB{\mathbf{c}}$ 和算术秘密共享的向量 $\share{\mathbf{x}}^{l}$，输出向量 $\share{\mathbf{y}}^{l}$。如果 $c_{i} = 1$，那么 $\share{y_i}^{l}=\share{x_i}^{l}$；否则 $y_i=\share{0}^{l}$。
    
    \item \textbf{布尔共享转换到算术共享：}
    $\mathcal{F}^{\BtoA}_{l}(\shareB{\mathbf{x}})$ 输入向量 $\mathbf{x}$ 的布尔秘密共享 $\shareB{\mathbf{x}}$，输出各元素位宽为 $l$ 的算术秘密共享 $\share{\mathbf{x}}^{l}$。
    
    \end{itemize}

\subsection{函数秘密共享}

\subsubsection{函数秘密共享算法定义}

一个函数秘密共享（Function Secret Sharing，FSS）协议是一对算法$(\gen,\eval)$。算法$\gen$将一个函数$g:\mathbb{G}^{\sfin}\rightarrow\mathbb{G}^{\sfout}$分成两个函数$(g_{0},g_{1})$。算法$\eval$以参与方身份标识$b\in\set{0,1}$和函数的秘密共享份额$g_{b}$作为输入，并且在输入$x\in\mathbb{G}^{\sfin}$上计算$g_{b}$。对于每个输入$x$，算法正确性要求$g_{0}(x)+g_{1}(x)=g(x)$。而函数秘密共享方案的安全性要求每个函数$g_{b}$隐藏要计算的函数$g$。
函数秘密共享的形式化定义为：

\begin{definition}
一个（两方的）函数秘密共享协议是一对算法$(\gen,\eval)$，使得
\begin{itemize}
    \item $\gen(1^{\lambda},\hat{g})$是一个概率多项式时间密钥生成算法，给定$1^{\lambda}$和$\hat{g}\in\set{0,1}^*$（函数$g$的描述），输出一对密钥$(k_{0},k_{1})$。该算法假设 $\hat{g}$显式地包含输入和输出的群$\mathbb{G}^{\sfin}$和$\mathbb{G}^{\sfout}$的描述。
    \item $\eval(b,k_{b},x)$是一个多项式时间评估算法，给定$b\in\set{0,1}$（参与方索引），$k_{b}$（定义$g_{b}: \mathbb{G}^{\sfin}\rightarrow\mathbb{G}^{\sfout}$的密钥）和$x\in\mathbb{G}^{\sfin}$（$g_{b}$的输入），输出$y_{b}\in\mathbb{G}^{\sfout}$（$g_{b}(x)$的值）。
\end{itemize}
\end{definition}

$\gen$输出的密钥$k_{0}$和$k_{1}$称为FSS密钥。$k_0$或$k_1$的比特数就是分析算法开销时所关注的密钥大小，并且对应于单个评估者需要存储的预处理的内容。这里假设$g$的输出域是有限阿贝尔群$\mathbb{G}$，可以在上面进行加法。虽然这可以通过将$g$的真值表秘密共享来简单地解决，但函数秘密共享的目标是，使用更短的密钥$k_0$和$k_1$来得到$g_0$和$g_1$的简洁的描述，同时仍然允许对其进行有效计算。因此，多数工作都在优化函数秘密共享的密钥大小，以及减少主要的计算成本——伪随机函数的调用。

\subsubsection{函数秘密共享用于安全两方计算}


函数秘密共享是一个$(2+1)$方的半诚实安全两方计算模型，也就是具有一个诚实的辅助方的半诚实安全两方计算模型。安全地计算函数秘密共享电路的协议包括两个阶段：离线阶段（预处理阶段）和在线阶段。其中离线阶段需要一个辅助的密钥发放方（称为dealer）来生成随机密钥，在线阶段只由两个参与方使用密钥进行计算。


\textbf{离线阶段（预处理阶段）：} 对于计算拓扑的电路中每个导线$w_{i}$，密钥发放方随机选择一个掩码$r_{i}$。对于每个门（子协议）$\pname{g}$，输入导线为$w_{i}$且输出导线为$w_{j}$，密钥发放方执行$\fssgen{g}{}$，以生成偏移函数（offset function）$g^{[r_{i},r_{j}]}(x)=g(x-r_{i})+r_{j}$ 的函数秘密共享密钥$(k^{g}_{0},k^{g}_{1})$，并且将$k^{g}_{b}$给参与方$b\in\set{0,1}$。并且，对于输入导线$w_{i}$，如果它是参与方$b$所拥有，那么密钥发放方向该参与方$b$发送相应的掩码$r_{i}$。

\textbf{在线阶段：} 对于每个输入导线$w_{i}$，其输入值为$x_{i}$，如果由参与方$P_{b}$所拥有，那么$P_{b}$计算$\hat{x}_{i}=x_{i}+r_{i}$并将$\hat{x}_{i}$发送给对方$P_{1-b}$。然后从输入门开始，双方根据已知的计算拓扑，按照电路顺序依次评估各个门，以得到各个门加了掩码的输出导线的值。为了处理具有输入导线$w_i$、输出导线$w_j$和加掩码的输入导线值$\hat{x}_{i}=x_{i}+r_{i}$的门$g$，参与方$b$使用$\eval$和$k^{g}_{b}$与$\hat{x}_{i}$来计算加掩码的输出导线值的秘密共享份额$\hat{x}_{j}=g^{[r_{i},r_{j}]}(\hat{x}_{i})=g(\hat{x}_{i}-r_{i})+r_{j}=g(x_{i})+r_{j}=x_{i}+r_{j}$。每个门评估之后，双方通过一轮交互来重建得到加掩码的输出导线值$\hat{x}_{j}$。对于整个计算拓扑的输出导线，指定的拥有输出的参与方可以从密钥发放方接收相应掩码，并在$\hat{x}_{j}$上减去掩码$r_{j}$，以获得明文（不加掩码）的最终输出值${x}_{j}$。

\textbf{协议构建：} 本论文使用$\hat{x}$表示一个加了掩码的变量$x$。考虑一个函数$\mathsf{F}$，其中$y=\mathsf{F}(x)$，对应于$\mathsf{F}$的协议表示为$\protocol{F}$，它有两个阶段的协议$(\fssgen{F}{},\fsseval{F}{})$。$\keysize{\protocol{F}}$表示存储由$\fssgen{F}{}$生成的$\protocol{F}$的密钥所需的比特位数。在线阶段，$\protocol{F}$产生掩码输出值的秘密共享份额$\hat{y} = y + \fssout$。特别地，本论文定义一个符号$\protocolTilde{F}$表示使用$\fssout = 0$ 来执行 $\fssgen{F}{}$，这使得 $\protocolTilde{F}$ 在在线阶段会输出未加掩码的$y$的秘密共享。


\textbf{函数秘密共享中密钥发放方的实现：} 

函数秘密共享协议是在一个理想的预处理模型中提出的，其中两个计算参与方在离线阶段从诚实的密钥发放方那里接收相关的随机密钥。该理想模型中的协议可以在没有密钥发放方的情况下，通过不同的通用方法转换为标准模型中的协议。此类转换的方法包括：

\begin{enumerate}
    \item 三方设置：给定三方且其中一方可能被攻破，密钥发放方的角色可以被第三方直接模拟。
    \item 使用可信硬件的两方设置：密钥发放方的角色可以在可信执行环境中模拟，例如Intel SGX~\cite{mckeen2013innovative}提供的环境。
    \item 两方设置：密钥发放方的角色可以由两个参与方通过安全两方协议共同模拟。
\end{enumerate}

在实际应用中，前两种方法对于预计算而言效率最高。第一种方法需要一个额外的不共谋的参与方，第二种方法需要可信硬件的辅助。而第三种方法的效率依赖于其他的安全协议执行预计算过程，离线成本较高。本论文忽略密钥发放方的设置，而在实现中主要在离线阶段采用三方设置。

\subsubsection{分布式比较函数和双重分布式比较函数}\label{subsec:ddcf}


一个比较函数$f^{<}_{\alpha,\beta}$定义为函数$f^{<}:\mathbb{G}^{\sfin}\rightarrow\mathbb{G}^{\sfout}$，其中$\alpha\in\mathbb{G}^{\sfin}$且$\beta\in\mathbb{G}^{\sfout}$，使得如果$x<\alpha$，输出$f^{<}(\alpha)=\beta$，否则$f^{<}(x)=0$。一个分布式比较函数是一个对于所有比较函数族的函数秘密共享方案$(\gen^{<},\eval^{<})$，具有默认的泄露$\mathsf{Leak}(\hat{f^{<}})=(\mathbb{G}^{\sfin},\mathbb{G}^{\sfout})$。Boyle等人~\cite{boyle2016function,boyle2021Function}基于函数秘密共享，提出了分布式比较函数（Distributed Comparison Function，DCF）。

双重分布式比较函数（Dual Distributed Comparison Function，DDCF）是Boyle等人~\cite{boyle2021Function}提出的分布式比较函数的扩展协议。它定义了一个比较函数$f^\DDCF_{\alpha,\beta_{1},\beta_{2}}: \set{0,1}^{n}\rightarrow \mathbb{G}$，当输入值小于$\alpha$时返回$\beta_{1}$，否则返回$\beta_{2}$。双重分布式比较函数可以通过分布式比较函数表示为$f^\DDCF_{\alpha,\beta_{1},\beta_{2}}(x)=\beta_{2}+f^\mathsf{<}_{\alpha,\beta_{1}-\beta_{2}}(x)$。本论文使用$\fssgen{DDCF}{n}(\alpha,\beta_{1},\beta_{2},\mathbb{G})$和$\fsseval{DDCF}{n}(b,k_{b},x)$来表示DDCF的FSS算法。为了清晰和方便起见，本论文采用符号$\DCF_{n,\mathbb{G}}$和$\DDCF_{n,\mathbb{G}}$来指代分布式比较函数和双重分布式比较函数的函数秘密共享协议的成本，包括密钥大小和计算开销。$\DDCF_{n,\mathbb{G}}$的密钥大小等于$\DCF_{n,\mathbb{G}}$的密钥大小加上$\lceil \log{|\mathbb{G}|} \rceil$比特。

\section{同态加密}\label{section:preliminaties_he}

同态加密（Homomorphic Encryption，HE）是指这样一类密码算法，对消息的密文执行某些运算，其结果解密后可以得到对消息明文进行对应运算后的结果，例如加法或乘法运算。随着同态加密相关研究的不断深入，已经有多种实用的同态加密方案提出，并得到了广泛应用。常用的同态加密方案的类型包括加性同态加密（Additive-HE，AHE），只支持加法同态运算，典型的方案代表为Paillier同态加密方案~\cite{paillier1999public}；层次同态加密（Leveled-HE，LHE），支持加法和有限深度的乘法同态运算，典型的方案代表为Brakerski-Fan-Vercauteren （BFV）同态加密方案~\cite{fan2012somewhat}和Brakerski-Gentry-Vaikuntanathan（BGV）同态加密方案~\cite{brakerski2014leveled}等，其中层次是一个可调参数，会影响密文大小和同态操作的效率。本论文主要使用了Paillier同态加密方案和BFV同态加密方案。

\subsection{Paillier同态加密系统}

Paillier密码系统~\cite{paillier1999public}是最流行的同态加密方案之一，可以实现加法同态运算。具体而言，Paillier密码系统主要包括以下三种最关键的算法：

\begin{itemize}
    \item 密钥生成：随机且独立地选取两个大的素数 $p$ 和 $q$，计算 $\lambda=\lcm(p-1,q-1)$ 和 $N=pq$，其中 $\lambda$ 是 $p-1$ 和 $q-1$ 的最小公倍数。定义函数$\paillierL(x)=(x-1)/N$，选择生成元 $g=(1+N)$，然后计算 $\mu={(\paillierL(g^{\lambda}\mod N^{2}))}^{-1} \mod N$。那么公钥是$\pk=(N,g)$，私钥是 $\sk=(\lambda,\mu)$。
    \item 加密 $E_{\pk}(m)\rightarrow c$：给定消息 $m\in\mathbb{Z}^{*}_{N}$ 和公钥 $\pk=(N,g)$，随机选择 $r\in\mathbb{Z}^{*}_{N}$，计算密文 $c=g^{m}r^{N}\mod N^{2}$。
    %    然后，SP计算和$\mu={(\paillierL(g^{\lambda}\mod N^{2}))}^{-1} \mod N$，其中$\paillierL(x)=(x-1)/N$。私钥为$\sk=(\lambda,\mu)$。
    \item 解密 $D_{\sk}(c)\rightarrow m$：给定密文 $c\in\mathbb{Z}^{*}_{N^{2}} $，使用私钥 $\sk=(\lambda,\mu)$，可以计算得到明文 $m=\paillierL(c^{\lambda}\mod N^{2})\cdot\mu\mod N$。
\end{itemize}

% 为了方便，我们使用$$表示，
Paillier密码系统具有加法同态性质，即分别给定消息 $m_{1}$ 和 $m_{2}$ 使用同一公钥$\pk=(N,g)$加密的密文 $c_{1}=E_{\pk}(m_{1})$ 和 $c_{2}=E_{\pk}(m_{2})$，可以通过计算乘积 $c_{1}c_{2}\mod N^{2}$ 来获得 $m_{1}+m_{2}$ 的密文$E_{\pk}(m_{1}+m_{2})$。这样的加性同态加密算法还支持密文与明文的乘法操作，也即分别给定消息 $m$ 的密文$c=E_{\pk}(m)$ 和一个明文 $k$，可以通过计算 $c^{k}\mod N^{2}$ 来获得 $km$ 的密文$E_{\pk}(km)$。

\subsection{BFV同态加密系统}\label{sec:bfv}


\subsubsection{BFV同态加密方案}

BFV 同态加密方案~\cite{fan2012somewhat} 是一个基于格问题中环上容错学习问题 （Ring Learning with Errors Problem, RLWE）的同态加密方案，支持加法和乘法的同态运算。
BFV方案的密文空间是 $R_{q}=\mathbb{Z}_{q}[X]/(X^{n}+1)$，它是系数在$\mathbb{Z}_{q}$中且模$(X^{n}+1)$的多项式的商环，其中 $q$ 是一个整数，$n$ 为格的维度且是2的幂。明文的消息空间是 $R_t=\mathbb{Z}_{t}[X]/(X^{n}+1)$，其中 $t$ 是一个整数且满足 $t<q$。然后定义$\Delta=\lfloor q/t \rfloor$，为$q$除以$t$的整数。
BFV方案从两个不同的分布中采样，密钥分布表示为 $R_{3}=\mathbb{Z}_{3}[X]/(X^{n}+1)$，其中系数均匀分布在$\{-1,0,1\}$中。$R_q$ 上的误差分布 $\chi$ 的系数服从中心化离散高斯分布，标准差为 $\sigma$，且在 $[-B,B]$ 上截断，其中 $\sigma$ 和 $B$ 是两个密码系统的参数。

在本论文中使用的BFV方案最常见的原语如下：

\begin{itemize}
\item 私钥生成 $\bfvSecKeyGen(pp)\rightarrow\sk$：给定BFV加密系统的公共参数 $pp$，采样 $s \leftarrow R_{3}$。输出 $\sk=s$。
\item 公钥生成 $\bfvPubKeyGen(\sk)\rightarrow\pk$：令私钥 $\sk=s$，采样 $p_{1}\leftarrow R_{q}$ 和 $e\leftarrow\chi$。输出公钥 $\pk=(p_{0},p_{1})=(-sp_{1}+e,p_{1})$。
\item 使用公钥加密 $\bfvEnc(\pk,m)\rightarrow\ct$：令公钥 $\pk=(p_{0},p_{1})$，采样 $u\leftarrow R_{3}$ 和 $e_{0},e_{1}\leftarrow\chi$。输出密文 $\ct=(\Delta m + u p_{0} + e_{0},u p_{1} + e_{1})$。
\item 使用私钥解密 $\bfvDec(\sk,\ct)\rightarrow m$：令私钥 $\sk=s$，采样 $\ct=(c_{0},c_{1})$。输出消息 $m'={\left[\left\lfloor\frac{t}{q}{\left[c_{0}+c_{1}s\right]}_{q}\right\rceil\right]}_{t}$。

\item 同态操作：本论文用``$\bfvAdd$''和``$\bfvMul$''分别表示同态加法和乘法。BFV方案支持
\begin{align}
    \bfvDec(\ct_{a}\bfvAdd\ct_{b})=a+b \mod ((X^n+1),t)\\
    \bfvDec(\ct_{a}\bfvMul\ct_{b})=a\times b \mod ((X^n+1),t)
\end{align}
其中，$\ct_{a}$ 和 $\ct_{b}$ 分别是消息 $a,b\in R_t$ 的密文。

\end{itemize} 

\subsubsection{多方BFV同态加密方案}\label{sec:mbfv}

多方同态加密是同态加密方案在多门限和多密钥下的变体，可以用于构建同态加密在安全多方计算中的方案。Mouchet等人提出的多方BFV（Multiparty BFV，MBFV）方案~\cite{mouchet2021multiparty}是BFV方案的一个多方扩展方案，可以支持分布式的解密，以及在同态加密的密文和线性的秘密共享之间构建转换的桥梁。其方案中各方的通信复杂度和计算电路的输入和输出规模线性相关，协议执行也不需要端到端的安全信道。本论文采用Mouchet等人提出的MBFV方案来实现密钥分离设计。特别地，本论文主要采用两方的设置，两个计算参与方分别为$P_{0}$和$P_{1}$。方案假设它们之间存在一个经过认证的信道，并且它们都可以访问一个随机的共同引用字符串（Common Reference String，CRS）。本论文主要使用的MBFV方案中的算法和协议如下：

\begin{itemize}
    \item 私钥生成。 $\mbfvSecKeyGen(pp)\rightarrow\sk_i$： 给定公共参数 $pp$，对于 $i\in\{0,1\}$，参与方 $P_i$ 使用BFV方案的私钥生成算法生成自己的私钥份额 $\sk_i\leftarrow \bfvSecKeyGen(pp)$。

    \item 集体加密密钥生成。 $\mbfvEncKeyGen(\sk_{0},\sk_{1})\rightarrow\cpk$： $P_0$ 和 $P_1$ 使用各自的私钥份额 $\sk_{0},\sk_{1}$ 一起生成一个集体加密密钥（Collective Encryption-Key）$\cpk$。

    \item 公钥转换。 $\mbfvPubKeySwitch(\ct, \pk', \sk_{0},\sk_{1})\rightarrow\ct'$： 给定一个使用集体加密密钥 $\cpk$ 所加密的密文 $\ct$ ，以及一个私钥 $\sk'$ 所对应的输出的公钥 $\pk'$， $P_0$ 和 $P_1$ 一起重新使用 $\sk'$ 的密钥重新加密 $\ct$。
\end{itemize}

MBFV 方案还提供了用于在BFV的密文和加法秘密共享之间转换的协议  $\mbfvEtoS$ 和 $\mbfvStoE$。对于本论文采用的安全两方计算的设置，这些协议只需要一轮交互。

\begin{itemize}
    \item BFV密文转换到秘密共享。 $\mbfvEtoS(\ct,\sk_{0},\sk_{1})\rightarrow M_i$：给定一个消息 $m\in R_t$ 的密文 $\ct$，对于 $i\in\{0,1\}$，为 $P_i$ 生成其在 $R_t$ 上的加法秘密共享 $M_i$，其中 $m=M_{0}+M_{1}$。

    \item 秘密共享转换到BFV密文。 $\mbfvStoE(M_{0}, M_{1},\sk_{0}, \sk_{1})\rightarrow \ct$：给定$P_0$ 和 $P_1$ 各自持有的秘密共享 $M_{0}$、$M_{1}$ 以及私钥份额 $\sk_{0}$、$\sk_{1}$，对于 $i\in\{0,1\}$， $P_i$ 输入其对 $M_i$ 和 $sk_i$ 的秘密份额，共同产生使用集体加密密钥 $\cpk$ 加密的消息 $m$ 的密文 $\ct$。
\end{itemize}


\subsubsection{消息打包方式}

BFV方案中消息打包是将数据向量编码为 BFV 方案中的明文多项式，从而实现向量化的同态运算。SIMD 打包~\cite{smart2014fully}可以实现逐元素的加法和乘法。此外，一些方案~\cite{huang2022cheetah,zhao2020smart}采用无 SIMD 的打包方法，通过精心设置明文多项式的系数来进行多项式的加法或乘法运算，进而可以更高效地实现向量内积等运算。


\section{真值发现算法}\label{section:preliminaties_td}

在群智感知场景中，对于一个被感知的对象，数据可以从多个数据提供者处收集。然而，不同来源的数据之间往往可能存在冲突，收集到的数据被一些不可靠的噪声信息干扰而质量层次不齐，呈现异质性。为了从这些不足够准确、可靠的数据中提取真实信息，传统数据聚合方法通常对所有信息源一视同仁，并通过平均值或者投票法得出最终结果。真值发现（Truth Discovery，TD）算法有助于解决这种多源数据的异质性问题。真值发现算法根据不同数据源上传的数据之间的不同可靠性程度推断出真实的信息。目前，已经有许多真值发现算法被提出。尽管算法细节彼此略有不同，但为每个数据源根据上传的数据分配权重，然后依赖加权平均来估计地面真值的基本原理是基本相同的。基于异质数据冲突解决（Conflict Resolution on Heterogeneous Data，CRH）~\cite{li2014resolving}的真值发现算法在许多隐私保护真值发现的工作中得到了广泛的应用。因此，这里介绍基于CRH算法的真值发现过程。


真值发现算法中，首先为各个感知对象$m$初始化随机的地面真值$t_m$，然后迭代地执行权重估计步骤和真值估计步骤的计算，直到估计的真值满足收敛标准。收敛标准可以是预定义的迭代次数，也可以是连续两次迭代中估计的地面真值之间距离的阈值。假如系统中有$K$个用户，有$M$个感知对象，那么算法的主要流程为：

\begin{itemize}
    \item 权重估计：在这个步骤中，计算每个用户（例如用户$k$）的权重。给定感知对象$m$的估计的地面真值$t_m$，权重$w_k$可以通过下式得到：
    \begin{equation}\label{equ:PPTD_weight}
    w_k=\log\frac{\sum_{k=1}^{K}{\sum_{m=1}^{M}{d(x_{m,k},t_{m})}}}{\sum_{m=1}^{M}{d(x_{m,k},t_{m})}}
    \end{equation}
    其中，$d(x_{m,k},t_{m})$ 是用户数据 $x_{m,k}$ 和地面真值 $t_{m}$ 之间的距离函数。
    本论文主要关注连续型的感知数据，其中距离函数采用平方距离 $d(x_{m,k},t_{m})={(x_{m,k}-t_{m})}^{2}$。对于分类型的数据，每个数据点是在一个选项集合中选择一个答案，数据点可以表示为一个向量$x_{m,k}=(0,\ldots,\underset{q}{1},\ldots,1)$，表示选择的是第$q$个选项。那么分类数据的距离和连续型数据类似，可以表示为 $d(x_{m,k},t_{m})={(x_{m,k}-t_{m})}^{T}(x_{m,k}-t_{m})$。
    
    \item 真值估计：对于每个感知对象，根据本次迭代中对所有用户估计的权重$w_{k}$，对感知数据计算加权平均，得到本次迭代的地面真值
    \begin{equation}
        t_{m}=\frac{\sum_{k=1}^{K}{w_{k} x_{m,k}}}{\sum_{k=1}^{K}{w_k}}
    \end{equation}
\end{itemize}

\section{动态时间扭曲算法}\label{section:preliminaties_dtw}

动态时间扭曲（Dynamic Time Warping，DTW）算法~\cite{berndt1994using,rakthanmanon2012searching,begum2015accelerating}是一种用于时间序列数据匹配的经典距离度量算法，广泛应用于医学~\cite{hebbrecht2020understanding}、经济学~\cite{miljkovic2023linkages}和环境科学~\cite{moola2021vegetable}等领域的时间序列数据分析，例如用于基因组数据分析和利用心电图数据识别室性早搏。本节对DTW算法及其常用优化方法进行介绍。

令 $Q=(\mathbf{q}_{1},\ldots,\mathbf{q}_{|Q|})$ 表示请求者发送的长度为 $|Q|\in\mathbb{N}$ 的请求时间序列。类似的，让 $C=(\mathbf{c}_{1},\ldots,\mathbf{c}_{|C|})$ 表示长度为 $|C|\in\mathbb{N}$ 的候选时间序列序列。
这些序列由一系列 $\dim$ 维特征向量 $\mathbf{q}_{i},\mathbf{c}_{j}$，其中$i\in[1,|Q|]$和 $j\in[1,|C|]$组成。
只有当两个序列的特征向量具有相同的维数时，它们才是可比较的。让 $Q_{i}=(\mathbf{q}_{1},\ldots,\mathbf{q}_{i})$ 代表$Q$ 的子序列，同样，$C_{j}$ 也是如此。在不失一般性的前提下，本论文考虑具有整数个数据点的等长序列（即 $|Q|=|C|$）。本论文将包含 $n$ 序列的候选数据集表示为 $\mathbf{C}=\set{C^{1},\ldots,C^{n}}$。
给定两个时间序列 $Q$ 和 $C$ 作为输入，动态时间扭曲算法会输出一个表示两个序列之间距离的量，称为 DTW 距离，来衡量两个序列之间的相似性。通常情况下，动态时间扭曲基于动态规划算法进行计算。其基本原理是在每一步中，根据逐渐增长的子序列之间的最小累计距离确定最佳排列，直至达到两个序列的终点。

\textbf{DTW距离的基本算法：}\Cref{alg:dtw} 描述了动态时间扭曲算法。$\dist(\mathbf{q}_{i},\mathbf{c}_{j})$ 表示特征向量对之间的欧几里得距离。在\Cref{algline:minimum_cumulative_distance_begin}到\Cref{algline:minimum_cumulative_distance_end}中，符号 $\Dist(Q_{i},C_{j})$ 表示 $Q_{i}$ 和 $C_{j}$ 之间的最小累计距离。完整序列 $Q$ 和 $C$ 之间的 DTW 距离用 $\DTW(Q,C)=\Dist(Q_{|Q|},C_{|C|})$ 表示。
在实际应用中为了降低使用DTW算法进行时序数据分析的开销，会引入约束条件和使用下界函数来减少计算量。

\begin{algorithm}[ht]
    \caption{DTW距离的基础算法}\label{alg:dtw}
    \Input{请求序列$Q=(\mathbf{q}_{1},\ldots,\mathbf{q}_{|Q|})$，候选序列 $C = (\mathbf{c}_{1},\ldots,\mathbf{c}_{|C|})$；}
    \Output{$Q$ 和 $C$ 之间的 DTW 距离 $\DTW(Q,C)$；}
    \For{$i\in[1,|Q|], j\in[1,|C|]$}{
        $\dist(\mathbf{q}_{i},\mathbf{c}_{j})\leftarrow {(\mathbf{q}_{i}-\mathbf{c}_{j})}^{2}$；\\
        
        \uIf{$i==1$ 且 $j==1$\label{algline:minimum_cumulative_distance_begin}}
        {$\Dist(Q_{1},C_{1})\leftarrow \dist(\mathbf{q}_{1},\mathbf{c}_{1})$；}
        \uElseIf{$i==1$}
        {$\Dist(Q_{1},C_{j})\leftarrow \dist(\mathbf{q}_{1},\mathbf{c}_{j})+\Dist(Q_{1},C_{j-1})$；}
        \uElseIf{$j==1$}
            {$\Dist(Q_{i},C_{1})\leftarrow \dist(\mathbf{q}_{i},\mathbf{c}_{1})+\Dist(Q_{i-1},C_{1})$；}
        \Else{
            $\Dist(Q_{i},C_{j})\leftarrow \dist(\mathbf{q}_{i},\mathbf{c}_{j})+\min\{\Dist(Q_{i-1},C_{j-1}),\Dist(Q_{i},C_{j-1}),\Dist(Q_{i-1},C_{j})\}$；\\
        }\label{algline:minimum_cumulative_distance_end}}
    $\DTW(Q,C)=\Dist(Q_{|Q|},C_{|C|})$；
    \end{algorithm}




\subsubsection{全局约束和本地约束}

在 DTW 算法的应用中，一种普遍的方法是施加约束，包括全局约束和局部约束。全局约束可用于防止病态扭曲，即一个序列中相对较小的部分映射到另一个序列中相对较大的部分。此外，全局约束还能在一定程度上加快 DTW 距离的计算。如\Cref{fig:global_constraint} 所示，Sakoe-Chiba band 和 Itakura parallelogram 是最常用的两种全局约束。这些约束将允许的扭曲路径限制在指定区域内，图示中的灰色区域即为这些区域。
    
\begin{figure}[ht]
    \centering
    \subcaptionbox{Sakoe-Chiba band}{
    \begin{tikzpicture}
        \tikzmath{
            \step = 7;
            \NumBlock = 16;
            \BlockLength = \NumBlock*\step;
            \SCcr=5;
            \SCcrLength = \SCcr*\step;
            };
        \filldraw[fill=gray!20](0,\SCcrLength pt) -- (\BlockLength-\SCcrLength pt,\BlockLength pt) -- (\BlockLength pt,\BlockLength pt) -- (\BlockLength pt,\BlockLength-\SCcrLength pt) -- (\SCcrLength pt,0) -- (0,0) -- (0,\SCcrLength pt);
        \draw[help lines, color=black!50, step=\step pt](0,0) grid (\BlockLength pt,\BlockLength pt);
        \draw[black,decoration={brace, amplitude=3pt}, decorate] ([xshift = 1pt]\BlockLength pt,\BlockLength pt)--([xshift = 1pt]\BlockLength pt,\BlockLength-\SCcrLength pt) node[midway, right=1pt]{cr};
        \draw[black] node at (-\step pt,\BlockLength/7*5 pt) [left] {Q};
        \draw[black] node at (\BlockLength/7*5 pt,\BlockLength pt) [above=2pt] {C};
        \draw plot[smooth] coordinates {(0,\BlockLength+10 pt) (\BlockLength/7*1 pt,\BlockLength+4 pt) (\BlockLength/7*2 pt,\BlockLength+15 pt) (\BlockLength/7*3 pt,\BlockLength+5 pt) (\BlockLength/7*4 pt,\BlockLength+10 pt) (\BlockLength/7*5 pt,\BlockLength+2 pt) (\BlockLength/7*6 pt,\BlockLength+13 pt) (\BlockLength pt,\BlockLength+2 pt)};
        \draw plot[smooth] coordinates {(-10 pt,0 pt) (-5 pt, \BlockLength/7*1 pt) (-10 pt, \BlockLength/7*2 pt) (-2 pt, \BlockLength/7*3 pt) (-15 pt, \BlockLength/7*4 pt) (-2 pt, \BlockLength/7*5 pt) (-13 pt, \BlockLength/7*6 pt) (-5 pt, \BlockLength pt)};

    \end{tikzpicture}
    }
    \subcaptionbox{Itakura Parallelogram}{
    \begin{tikzpicture}
        \tikzmath{
            \step = 7;
            \NumBlock = 16;
            % \step = 4;
            % \NumBlock = 24;
            \BlockLength = \NumBlock*\step;
            \IPp = 2;
            int \IPBlock;
            \IPBlock = \NumBlock/(\IPp+1);
            \IPLength = \IPBlock*\step;
            };
        \filldraw[fill=gray!20](0,0) -- (\IPLength*2pt,\IPLength pt) -- (\BlockLength pt,\BlockLength pt) -- (\IPLength pt,\IPLength*2pt) -- (0,0);
        \draw[help lines, color=black!50, step=\step pt](0,0) grid (\BlockLength pt,\BlockLength pt);
        \draw[black] node at (-\step pt,\BlockLength/7*5 pt) [left] {Q};
        \draw[black] node at (\BlockLength/7*5 pt,\BlockLength pt) [above=2pt] {C};
        \draw plot[smooth] coordinates {(0,\BlockLength+10 pt) (\BlockLength/7*1 pt,\BlockLength+4 pt) (\BlockLength/7*2 pt,\BlockLength+15 pt) (\BlockLength/7*3 pt,\BlockLength+5 pt) (\BlockLength/7*4 pt,\BlockLength+10 pt) (\BlockLength/7*5 pt,\BlockLength+2 pt) (\BlockLength/7*6 pt,\BlockLength+13 pt) (\BlockLength pt,\BlockLength+2 pt)};
        \draw plot[smooth] coordinates {(-10 pt,0 pt) (-5 pt, \BlockLength/7*1 pt) (-10 pt, \BlockLength/7*2 pt) (-2 pt, \BlockLength/7*3 pt) (-15 pt, \BlockLength/7*4 pt) (-2 pt, \BlockLength/7*5 pt) (-13 pt, \BlockLength/7*6 pt) (-5 pt, \BlockLength pt)};
    \end{tikzpicture}
    }
    \caption{DTW算法的全局约束示例}\label{fig:global_constraint}
\end{figure}

局部约束可以根据特定领域的知识来设计，也可以通过试错的过程根据经验得出。Keogh 和 Ratanamahatana 等人~\cite{keogh2005exact}在全局约束的背景下重新解释了局部约束，并确定两者可以同时使用。在两者冲突的情况下，优先采用更严格的约束。\Cref{fig:local_constraint} 展示了 Sakoe 和 Chiba 等人建议采用的几种局部约束~\cite{sakoe1978dynamic}。例如，\Cref{fig:local_constraint_b} 中展示的约束条件将\Cref{alg:dtw} 中\Cref{algline:minimum_cumulative_distance_end}的等式替换为了 $\Dist(Q_{i},C_{j})\leftarrow \dist(\mathbf{q}_{i},\mathbf{c}_{j})+\min\{\Dist(Q_{i-1},C_{j-1}),\Dist(Q_{i-2},C_{j-1}),\Dist(Q_{i-1},C_{j-2}),\Dist(Q_{i-3},C_{j-1}),\Dist($ $Q_{i-1},C_{j-3})\}$。

\begin{figure}[ht]
    \centering
    \subcaptionbox{P=0}{
        \begin{tikzpicture}
            \tikzmath{
                \pointpt = 3;
                \linept = 0.8;
                \halfstep = 9;
                \step = \halfstep*2;
                \NumBlock = 2;
                \BlockLength = \NumBlock*\step;
                };
            \draw[help lines, color=black!50, step=\step pt](0,0) grid (\BlockLength pt,\BlockLength pt);
            \foreach \i in {1,...,\NumBlock}
            {
                \foreach \j in {1,...,\NumBlock}
                {
                    \fill (\i*\step-\halfstep pt,\j*\step-\halfstep pt) circle (\pointpt pt);
                }
            }
            \draw[line width = \linept pt] (\halfstep pt,\halfstep pt) -- (\halfstep+\step pt,\halfstep+\step pt);
            \draw[line width = \linept pt] (\halfstep+\step pt,\halfstep pt) -- (\halfstep+\step pt,\halfstep+\step pt);
            \draw[line width = \linept pt] (\halfstep pt,\halfstep+\step pt) -- (\halfstep+\step pt,\halfstep+\step pt);
        \end{tikzpicture}
    }
    \subcaptionbox{P=1/2\label{fig:local_constraint_b}}{
        \begin{tikzpicture}
            \tikzmath{
                \pointpt = 3;
                \linept = 0.8;
                \halfstep = 9;
                \step = \halfstep*2;
                \NumBlock = 4;
                \BlockLength = \NumBlock*\step;
                };
            \draw[help lines, color=black!50, step=\step pt](0,0) grid (\BlockLength pt,\BlockLength pt);
            \foreach \i in {1,...,3}
            {
                \foreach \j in {1,...,3}
                {
                    \ifthenelse{ \i = 3 \OR \j = 3}{
                        \fill (\i*\step-\halfstep pt,\j*\step-\halfstep pt) circle (\pointpt pt);
                        \fill (\i*\step+\halfstep pt,\j*\step+\halfstep pt) circle (\pointpt pt);
                        \draw[line width = \linept pt] (\i*\step-\halfstep pt,\j*\step-\halfstep pt) -- (\i*\step+\halfstep pt,\j*\step+\halfstep pt);
                        }{}

                }
            }
            \draw[line width = \linept pt] (\halfstep+\step pt,\halfstep+3*\step pt) -- (\halfstep+3*\step pt,\halfstep+3*\step pt);
            \draw[line width = \linept pt] (\halfstep+3*\step pt,\halfstep+\step pt) -- (\halfstep+3*\step pt,\halfstep+3*\step pt);
        \end{tikzpicture}
    }
    \subcaptionbox{P=1}{
        \begin{tikzpicture}
            \tikzmath{
                \pointpt = 3;
                \linept = 0.8;
                \halfstep = 9;
                \step = \halfstep*2;
                \NumBlock = 3;
                \BlockLength = \NumBlock*\step;
                };
            \draw[help lines, color=black!50, step=\step pt](0,0) grid (\BlockLength pt,\BlockLength pt);
            \foreach \i in {1,...,2}
            {
                \foreach \j in {1,...,2}
                {
                    \ifthenelse{ \i = 2 \OR \j = 2}{
                        \fill (\i*\step-\halfstep pt,\j*\step-\halfstep pt) circle (\pointpt pt);
                        \fill (\i*\step+\halfstep pt,\j*\step+\halfstep pt) circle (\pointpt pt);
                        \draw[line width = \linept pt] (\i*\step-\halfstep pt,\j*\step-\halfstep pt) -- (\i*\step+\halfstep pt,\j*\step+\halfstep pt);
                        }{}

                }
            }
            \draw[line width = \linept pt] (\halfstep+\step pt,\halfstep+2*\step pt) -- (\halfstep+2*\step pt,\halfstep+2*\step pt);
            \draw[line width = \linept pt] (\halfstep+2*\step pt,\halfstep+\step pt) -- (\halfstep+2*\step pt,\halfstep+2*\step pt);
        \end{tikzpicture}
    }
    \subcaptionbox{P=2}{
        \begin{tikzpicture}
            \tikzmath{
                \pointpt = 3;
                \linept = 0.8;
                \halfstep = 9;
                \step = \halfstep*2;
                \NumBlock = 4;
                \BlockLength = \NumBlock*\step;
                };
            \draw[help lines, color=black!50, step=\step pt](0,0) grid (\BlockLength pt,\BlockLength pt);
            \foreach \i in {1,...,3}
            {
                    \fill (\i*\step-\halfstep pt,\i*\step+\halfstep pt) circle (\pointpt pt);
                    \fill (\i*\step+\halfstep pt,\i*\step-\halfstep pt) circle (\pointpt pt);
            }
            \fill (2*\step+\halfstep pt,2*\step+\halfstep pt) circle (\pointpt pt);
            \fill (3*\step+\halfstep pt,3*\step+\halfstep pt) circle (\pointpt pt);
            \draw[line width = \linept pt] (\halfstep pt,\halfstep+\step pt) -- (\halfstep+2*\step pt,\halfstep+3*\step pt);
            \draw[line width = \linept pt] (\halfstep+\step pt,\halfstep pt) -- (\halfstep+3*\step pt,\halfstep+2*\step pt);
            \draw[line width = \linept pt] (\halfstep+2*\step pt,\halfstep+2*\step pt) -- (\halfstep+3*\step pt,\halfstep+3*\step pt);
            \draw[line width = \linept pt] (\halfstep+2*\step pt,\halfstep+3*\step pt) -- (\halfstep+3*\step pt,\halfstep+3*\step pt);
            \draw[line width = \linept pt] (\halfstep+3*\step pt,\halfstep+2*\step pt) -- (\halfstep+3*\step pt,\halfstep+3*\step pt);
        \end{tikzpicture}
    }
    \caption{DTW算法的局部约束示例}\label{fig:local_constraint}
\end{figure}
    

\subsubsection{DTW算法的下界距离}

利用下界函数来消除候选集中不可能成为最终匹配结果的样本是加速基于 DTW 的时间序列相似性搜索的最有效的策略之一。关于 DTW 的下界问题已经进行了大量研究。Rakthanmanon 等人\cite{rakthanmanon2012searching}建议级联应用DTW距离的多种下界函数，特别是主张依次使用LB\_Kim~\cite{kim2001index}和LB\_Keogh~\cite{keogh2005exact}下界函数。本论文考虑将这两种常见的下界距离整合到所提出的方案中，并能够实现它们的高效计算。

给定查询序列 $Q$，上界序列 $U$ 由 $\mathbf{u}_{i} = \max(\mathbf{q}_{i-cr}: \mathbf{q}_{i+cr})$ 构成，下界序列 $L$ 由 $\mathbf{l}_{i} = \min(\mathbf{q}_{i-cr}: \mathbf{q}_{i+cr})$组成。其中$cr$是一个由全局约束决定的值，它是公开的信息。
在Sakoe-Chiba band中，无论 $i$ 如何，$cr$ 保持不变；而在Itakura parallelogram中，$cr$ 是一个取决于 $i$ 的函数。
然后，$\mathrm{LB\_Keogh}(Q,C)$ 函数的定义如下：
\begin{equation}
    \mathrm{LB\_Keogh}(Q,C)=\sqrt{\sum_{i=1}^{|Q|}{
        \begin{cases}
        {(\mathbf{c}_{i}-\mathbf{u}_{i})}^{2} & \text{if}~\|\mathbf{c}_{i}\|> \|\mathbf{u}_{i}\| \\
        {(\mathbf{c}_{i}-\mathbf{l}_{i})}^{2} & \text{if}~\|\mathbf{c}_{i}\|< \|\mathbf{l}_{i}\| \\
        0 & \text{否则}
        \end{cases}
    }
    }\label{equ:FESCAT_LBKeogh}
\end{equation}

从每个序列 $Q$ 和 $C$ 中可以提取一个包含 4 个元素的特征向量，其中包括序列中第一个和最后一个，以及最大和最小的值。然后就可以根据这些特征计算出下界距离 $\mathrm{LB\_Kim}(Q,C)$，计算公式如下：
\begin{equation}
    \mathrm{LB\_Kim}(Q,C)=\max{
        \begin{cases}
            |\text{First}(C)-\text{First}(Q)|\\
            |\text{Last}(C)-\text{Last}(Q)|\\
            |\text{Greatest}(C)-\text{Greatest}(Q)|\\
            |\text{Smallest}(C)-\text{Smallest}(Q)|
        \end{cases}
    }\label{equ:FESCAT_LBKim}
\end{equation}

LB\_Kim的变体，如
\begin{equation}
\mathrm{LB\_KimFL}(Q,C)=\max(|\text{First}(C)-\text{First}(Q)|,|\text{Last}(C)-\text{Last}(Q)|)
\end{equation}
可以采用类似的方法进行协议设计。本论文将不再进一步阐述这些变体。

\section{本章小结}

本章介绍了本论文研究内容所需要的相关基础知识。首先，\Cref{section:preliminaties_mpc}介绍了本论文所使用的安全多方计算相关技术，包括秘密共享、不经意传输和函数秘密共享。\Cref{section:preliminaties_he}介绍了本论文所使用的同态加密相关技术，包括Paillier加法同态加密方案和BFV同态加密方案，以及BFV方案所扩展的多方同态加密方案。接着，\Cref{section:preliminaties_td}介绍了用于解决多源数据异质性问题的真值发现算法。最后，\Cref{section:preliminaties_dtw}介绍了用于时间序列数据分析的动态时间扭曲算法的基本原理和相关优化方法。